//给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
//
//
//
//
//
//
// 示例 1：
//
//
//输入：head = [4,2,1,3]
//输出：[1,2,3,4]
//
//
// 示例 2：
//
//
//输入：head = [-1,5,3,4,0]
//输出：[-1,0,3,4,5]
//
//
// 示例 3：
//
//
//输入：head = []
//输出：[]
//
//
//
//
// 提示：
//
//
// 链表中节点的数目在范围 [0, 5 * 10⁴] 内
// -10⁵ <= Node.val <= 10⁵
//
//
//
//
// 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
// Related Topics 链表 双指针 分治 排序 归并排序 👍 1451 👎 0

package leetcode.editor.cn;

import com.sicheng.algorithm.node.ListNode;

import java.util.PriorityQueue;

@SuppressWarnings("all")
//Java：排序链表
public class 排序链表 {
    public static void main(String[] args) {
        Solution solution = new 排序链表().new Solution();
        // TO TEST

    }
//leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null)
                return head;
            PriorityQueue<ListNode> heap = new PriorityQueue<>(((o1, o2) ->
                    o2.val - o1.val
            ));
            while (head != null) {
                heap.add(head);
                head = head.next;
            }
            ListNode h = heap.remove();
            h.next = null;
            while (!heap.isEmpty()) {
                ListNode node = heap.remove();
                node.next = h;
                h = node;
            }
            return h;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}
